#include "Graph.h"

void Graph::AddPath(int from, int to, int wegiht)
{
    nodeSet[from]->value = from;
    nodeSet[to]->value = to;
    ++nodeSet[from]->out;
    ++nodeSet[to]->in;
    edgeSet.push_back(new GraphEdge(nodeSet[from], nodeSet[to], wegiht));
    nodeSet[from]->nexts.push_back(nodeSet[to]);
    nodeSet[from]->edges.push_back(edgeSet.back());
}

void Graph_DFS(Graph* g, int nodeIdx)
{
    if(g->nodeSet[nodeIdx]->value == ErrVal)//空节点直接结束
        return;
    stack<GraphNode*> helpStk;//用栈辅助BFS过程
    unordered_set<int> nodeSet;//哈希表记录找到过的节点
    helpStk.push(g->nodeSet[nodeIdx]);//载入起始点
    nodeSet.insert(g->nodeSet[nodeIdx]->value);
    //处理DFS的序列，这里直接打印
    printf("%d",g->nodeSet[nodeIdx]->value);
    while(!helpStk.empty())
    {
        GraphNode *cur = helpStk.top();
        helpStk.pop();
        for(auto next : cur->nexts)
        {
            if(nodeSet.count(next->value) == 0)
            {
                helpStk.push(cur);
                helpStk.push(next);
                nodeSet.insert(next->value);
                //处理DFS序列
                printf("%d", next->value);
                break;
            }
        }
    }
}

void Graph_BFS(Graph* g, int nodeIdx)
{
    if(g->nodeSet[nodeIdx]->value == ErrVal)
        return;
    queue<GraphNode *> helpQue;
    unordered_set<int> nodeSet;
    helpQue.push(g->nodeSet[nodeIdx]);
    nodeSet.insert(g->nodeSet[nodeIdx]->value);
    while (!helpQue.empty())
    {
        GraphNode *cur = helpQue.front();
        helpQue.pop();
        //处理BFS序列
        printf("%d", cur->value);
        for(auto next : cur->nexts)
        {
            if(nodeSet.count(next->value) == 0)
            {
                helpQue.push(next);
                nodeSet.insert(next->value);
            }
        }
    }
}
